package main.java.Fzy.Test;

import java.util.Stack;

public class Test02 {


    public static void main(String[] args) {
        TestList testList = new TestList();
        testList.add(1);
        testList.add(2);
        testList.add(3);
        testList.add(9);
        testList.add(8);
        System.out.println("链表为：");
        testList.showList();
        System.out.println("倒数第K");
        System.out.println(testList.returnNum(2));
//        testList.showList();
    }
}
//链表的定义
class LinkListNode{
    int val;
    LinkListNode next;

    LinkListNode(int val){
        this.val = val;
    }
}

class TestList{

    LinkListNode head;


    //创建一个头结点
    TestList(){
        head = new LinkListNode(0);
    }

    //链表内添加元素
    public void add(int val){

        LinkListNode node  = new LinkListNode(val);

        LinkListNode cur = head;

        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }


    //返回链表倒数第K个元素
    public int returnNum(int k){

        //创建虚拟头结点

        LinkListNode dummyHead = new LinkListNode(0);

        //虚拟头结点指向传入链表头结点

        dummyHead.next = head;

        //定义快慢指针

        LinkListNode slowIndex = dummyHead;

        LinkListNode fastIndex = dummyHead;

        //快指针先移动k步

        while (k>0 && fastIndex !=null){

            fastIndex = fastIndex.next;

            k--;

        }

        fastIndex = fastIndex.next;

        //快慢指针同时向前移动

        while (fastIndex != null){

            fastIndex = fastIndex.next;

            slowIndex = slowIndex.next;

        }

        return slowIndex.next.val;

    }
    //显示

    public void showList(){

        if (head.next == null){

            System.out.println("链表已经让销毁");

        }

        //重虚拟头结点的下一个结点开始遍历

        LinkListNode cur = head.next;

        while (cur != null){

            System.out.print(cur.val+ " ");

            cur = cur.next;

        }
        System.out.println();

    }
}
